class PriorityQueue {

    constructor() {
        this.array = new Array(32);
        this.size = 0;
    }
    // 扩容
    resize() {
        let arrayNew = [].concat(this.array, new Array(this.array.length));
        this.array = arrayNew;
    }
    // 入队
    enQueue(key) {
        if (this.size >= this.array.length) {
            this.resize();
        }
        this.array[this.size++] = key;
        this.upAdjust();
    }
    // 出队
    deQueue() {
        if (this.size <= 0) {
            throw new Error('the queue is empty!');
        }
        let head = this.array[0];
        this.array[0] = this.array[this.size - 1];
        this.array[this.size - 1] = undefined;
        this.size--;
        this.downAdjust();
        return head;
    }
    // 上浮
    upAdjust() {
        let childIndex = this.size - 1;
        let parentIndex = Math.floor((childIndex - 1) / 2); // (10 - 1) / 2 => 4
        let temp = this.array[childIndex]; // 保存插入的叶子节点值，用于最后的赋值
        // 当 childIndex === 0 => root
        while (childIndex > 0 && temp > this.array[parentIndex]) {
            this.array[childIndex] = this.array[parentIndex];
            childIndex = parentIndex;
            parentIndex = Math.floor((parentIndex - 1) / 2); // (2 - 1) / 2 => 0
        }
        this.array[childIndex] = temp;
    }
    // 下沉
    downAdjust() {
        let parentIndex = 0;
        let temp = this.array[parentIndex]; // 保存父节点的值，用于最后的赋值
        let childIndex = 2 * parentIndex + 1;
        while (childIndex < this.size) { // 超过范围退出
            // 如果有右孩子，且右孩子大于左孩子，则定位到右孩子
            if ((childIndex + 1) < this.size && this.array[childIndex + 1] > this.array[childIndex]) {
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，直接跳出（上一步已经确保childIndex指向最大)
            if (temp >= this.array[childIndex]) break;
            this.array[parentIndex] = this.array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        this.array[parentIndex] = temp;
    }
}
let priorityQueue = new PriorityQueue();
priorityQueue.enQueue(3);
priorityQueue.enQueue(5);
priorityQueue.enQueue(10);
priorityQueue.enQueue(2);
priorityQueue.enQueue(7);
console.log('出队元素', priorityQueue.deQueue());
console.log('出队元素', priorityQueue.deQueue());